package Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;


public class FindPath {

	public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		// 思路大致上是寻找一条路径，如果该路径的和等于输入的值
		// 那么将其加入到List中，如果不等回到父节点并且遍历下一条路径
		// 由于回到父节点，想到要用栈的方式实现，由于递归的本质是栈，可使用递归
		Stack<Integer> stack = new Stack<>();
		findPath(root, target, 0, stack, list);
		return list;
	}

	public void relFindPath(TreeNode root, int target, int currentSum,
			ArrayList<Integer> path, ArrayList<ArrayList<Integer>> list) {
		currentSum += root.val;
		path.add(root.val);
		// 判断是否是叶子结点
		boolean isLeaf = root.left == null && root.right == null;
		if (currentSum == target && isLeaf) {
			list.add(path);
		}
		if (root.left != null) {
			relFindPath(root.left, target, currentSum, path, list);
		}
		if (root.right != null) {
			relFindPath(root.right, target, currentSum, path, list);
		}
		// 再返回父节点之前，将当前的结点值删除
		path.remove(path.size() - 1);

	}

	public void findPath(TreeNode root, int target, int currentSum,
			Stack<Integer> path, ArrayList<ArrayList<Integer>> list) {
		currentSum += root.val;
		path.push(root.val);
		// 判断是否是叶子结点
		boolean isLeaf = root.left == null && root.right == null;
		if (currentSum == target && isLeaf) {
			// 强制转换
			list.add((ArrayList<Integer>) Arrays.asList((Integer[]) path
					.toArray()));
		}
		if (root.left != null) {
			findPath(root.left, target, currentSum, path, list);
		}
		if (root.right != null) {
			findPath(root.right, target, currentSum, path, list);
		}
		// 再返回父节点之前，将当前的结点值删除
		path.pop();
	}
}
